#include<iostream>
#include<vector>

using namespace std;

class Node {
public:
	int val;
	Node* prev;
	Node* next;
	Node* child;
	Node() {}
	Node(int value) :val(value){}
};

class Solution {
public:

	Node* makeFlattenChain(Node *head,Node *child) {
		Node *tail = head, *temp = child;
		while (temp) {
			Node *node = new Node();
			node->val = temp->val;
			node->prev = tail;
			tail->next = node;
			if (temp->child)
				tail = makeFlattenChain(tail->next, temp->child);
			else tail = tail->next;
			temp = temp->next;
		}
		return tail;
	}

	Node* flatten(Node* head) {
		if (!head) return NULL;
		Node *myhead = new Node();
		Node *tail = myhead,*temp=head;
		while (temp) {
			Node *node = new Node();
			node->val = temp->val;
			node->prev = tail;
			tail->next = node;
			if (temp->child)
				tail = makeFlattenChain(tail->next, temp->child);
			else tail = tail->next;
			temp = temp->next;
		}
		myhead->next->prev = NULL;
		return myhead->next;
	}
};

void main() {
	Solution s;
	Node root(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7), n8(8), n9(9), n10(10), n11(11), n12(12);
	root.next = &n2;
	n2.next = &n3;
	n3.next = &n4;
	n4.next = &n5;
	n5.next = &n6;
	n3.child = &n7;
	n7.next = &n8;
	n8.next = &n9;
	n9.next = &n10;
	n8.child = &n11;
	n11.next = &n12;
	Node *mylist=s.flatten(&root);
	cout << "Done";
}